class Solution
{
public:
    int maxStudents(vector<vector<char>> &seats)
    {
        int m = seats.size();
        int n = seats[0].size();
        vector<int> masks;
        for (int i = 0; i < m; ++i)
        {
            int mask = 0;
            for (int j = 0; j < n; ++j)
            {
                if (seats[i][j] == '#')
                {
                    mask |= 1 << j;
                }
            }
            masks.push_back(mask);
        }

        int numState = (1 << n) - 1;

        auto validState = [&](int state, int row)
        {
            int mask = masks[row];
            if (state & mask)
            {
                return false;
            }
            if (state & (state << 1))
            {
                return false;
            }
            return true;
        };

        auto compatibleState = [](int currentState, int formerState)
        {
            currentState = currentState << 1;
            formerState = formerState << 1;
            if (formerState & (currentState << 1))
            {
                return false;
            }
            if (formerState & (currentState >> 1))
            {
                return false;
            }
            return true;
        };

        auto stuCount = [](int state)
        {
            return __builtin_popcount(state);
        };

        int result = 0;
        vector<int> dp(numState, -1);
        for (int state = 0; state < numState; ++state)
        {
            if (validState(state, 0))
            {
                dp[state] = stuCount(state);
            }
            result = max(result, dp[state]);
        }

        for (int row = 1; row < m; ++row)
        {
            vector<int> dpNew(numState, -1);
            for (int state = 0; state < numState; ++state)
            {
                if (!validState(state, row))
                {
                    continue;
                }
                for (int lastState = 0; lastState < numState; ++lastState)
                {
                    if (dp[lastState] == -1)
                    {
                        continue;
                    }
                    if (!compatibleState(state, lastState))
                    {
                        continue;
                    }
                    dpNew[state] = max(dpNew[state], dp[lastState] + stuCount(state));
                    result = max(result, dpNew[state]);
                }
            }
            dpNew.swap(dp);
        }
        return result;
    }

    // 超时
    int maxStudentsDfs(vector<vector<char>> &seats)
    {
        int m = seats.size();
        int n = seats[0].size();
        auto canSeat = [&](int row, int col) -> bool
        {
            if (seats[row][col] == '#')
            {
                return false;
            }
            if (col > 0)
            {
                if (seats[row][col - 1] == '1')
                {
                    return false;
                }
                if (row > 0 && seats[row - 1][col - 1] == '1')
                {
                    return false;
                }
            }
            if (col < n - 1)
            {
                if (seats[row][col + 1] == '1')
                {
                    return false;
                }
                if (row > 0 && seats[row - 1][col + 1] == '1')
                {
                    return false;
                }
            }
            return true;
        };

        function<int(int, int)> dfs = [&](int row, int col) -> int
        {
            if (row == m - 1 && col == n - 1)
            {
                return canSeat(row, col);
            }

            int nextRow = row;
            int nextCol = col + 1;
            if (nextCol == n)
            {
                nextCol = 0;
                nextRow += 1;
            }

            int result = dfs(nextRow, nextCol);

            if (canSeat(row, col))
            {
                seats[row][col] = '1';
                result = max(result, 1 + dfs(nextRow, nextCol));
                seats[row][col] = '.';
            }
            return result;
        };
        return dfs(0, 0);
    }
};